#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
	int value;
	struct node *next;
	struct node *sibling;
} node_t;

void create_list(node_t **h) 
{
	int i;
	node_t *node;
	node_t *arr[5];

	for (i = 0; i < 5; i++) {
		node = (node_t *)malloc(sizeof(node_t));
		arr[i] = node;
		memset(node, 0, sizeof(node_t));
		node->value = i;
		
		if (*h == NULL) {
			*h = node;
		} else {
			node->next = *h;
			*h = node;
		}
	}

	arr[4]->sibling = arr[2];
	arr[3]->sibling = arr[0];
	arr[1]->sibling = arr[3];
}

void print_list(node_t *h)
{
	node_t *p;
	
	for (p = h; p != NULL; p = p->next)
		printf("%d ", p->value);
	printf("\n");

	for (p = h; p != NULL; p = p->next)
		if (p->sibling)
			printf("%d sibling:%d\n", p->value, p->sibling->value);
}

void clone_next(node_t *h) 
{
	node_t *p, *new;

	if (NULL == h)
		return;
	p = h;
	while(p != NULL) {
		new = (node_t *)malloc(sizeof(node_t));
		memset(new, 0, sizeof(node_t));
		new->value = p->value;
	
		new->next = p->next;
		p->next = new;

		p = new->next;
	}
}

void clone_silbings(node_t *h)
{
	node_t *p;

	if (NULL == h || NULL == h->next)
		return;

	p = h;
	while (p != NULL) {
		if (p->sibling)  {
			node_t *q;

			q = p->next;
			q->sibling = p->sibling->next;
		}
		p = p->next->next;
	}
}

void reconnect(node_t *h1, node_t **h2) 
{
	node_t *p, **tail = h2;

	if (h1 == NULL || h1->next == NULL)
		return;
	
	p = h1;
	while (p != NULL) {
		node_t *q = p->next;
		p->next = q->next;
		q->next = NULL;
	
		*tail = q;
		tail = &(q->next);

		p = p->next;
	}
}

int main() 
{
	node_t *h1 = NULL, *h2 = NULL;

	create_list(&h1);
	printf("origin list h1::\n");
	print_list(h1);

	clone_next(h1);
	clone_silbings(h1);
	reconnect(h1, &h2);

	printf("after clone h1::\n");
	print_list(h1);
	printf("after clone h2::\n");
	print_list(h2);
	return 0;
}

